#define _CRT_SECURE_NO_WARNINGS
//#include<stdio.h>
//void power(int ans[], int a, int b)
//{
//	int i, j;
//	ans[0] = 1;
//	ans[1] = 1;
//	for (i = 2; i <= 4; i++)
//		ans[i] = 0;
//	for (i = 1; i <= b; i++)
//	{
//		int h = 0;
//		for (j = 1; j <= ans[0] && j <= 4; j++)
//		{
//			ans[j] = ans[j] * a + h;
//			h = ans[j] / 10;
//			ans[j] %= 10;
//		}
//		while (h)
//		{
//			ans[0]++;
//			ans[j++] += h % 10;
//			h /= 10;
//		}
//	}
//
//}
//void print(int a[])
//{
//	int i;
//	int sum = 0;
//	int f = 1;
//	for (i = 1; i <= 4; i++)
//	{
//		sum = sum + a[i] * f;
//		f *= 10;
//	}
//	printf("%d\n", sum);
//}
//void add(int  sum[], int t[])
//{
//	int i;
//	for (i = 1; i <= 4; i++)
//	{
//		sum[i] += t[i];
//		if (sum[i] >= 10)
//		{
//			sum[i + 1] += 1;
//			sum[i] %= 10;
//		}
//	}
//}
//int main()
//{
//	int N;
//	scanf("%d", &N);
//
//	while (N)
//	{
//		N--;
//		int a, b, i;
//		int sum[10] = { 0 }, t[10] = { 0 };
//		scanf("%d%d", &a, &b);
//		for (i = 1; i <= a; i++)
//		{
//			power(t, i, b);
//			add(sum, t);
//		}
//		print(sum);
//
//	}
//	return 0;
//}